package leetcode_1001_1100;

import java.util.Arrays;

public class LeeCode_1105 {
    public static void main(String[] args) {
        System.out.println(minHeightShelves(new int[][]{{1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}}, 4));
        System.out.println(minHeightShelves(new int[][]{{1, 3}, {2, 4}, {3, 2}}, 6));
    }
    private static int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int max = 0, con = 0;
            for(int j = i; j >= 0; j--){
                con += books[j][0];
                if (con > shelfWidth){
                    break;
                }
                max = Math.max(max, books[j][1]);
                dp[i + 1] = Math.min(dp[i + 1], dp[j] + max);
            }
        }
        return dp[n];
    }
}
